package 牛客.二叉树;

import 剑指offer.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class BM38在二叉树中找到两个节点的最近公共祖先 {
    //牛客要求返回 int，对节点.val记得要判空
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //递归代码
        return helper(root,o1,o2).val;
    }

    private TreeNode helper(TreeNode root, int o1, int o2) {
        if (root==null || root.val==o1 || root.val==o2) {
            return root;
        }

        TreeNode left=helper(root.left,o1,o2);
        TreeNode right=helper(root.right,o1,o2);

        if(left!=null && right!=null) {
            return root;
        }
        return left!=null ? left:right;
    }


    public int lowestCommonAncestor1 (TreeNode root, int o1, int o2) {
        // write code here
        Map<Integer, Integer> map = new HashMap<>();
        map.put(root.val, root.val);
        fun(root, map);

        //用Set 从下到上，遍历记录o1的祖先链
        Set<Integer> set = new HashSet<>();
        int cur = o1;
        while (map.get(cur) != cur) {
            set.add(cur);
            cur = map.get(cur);
        }
        set.add(cur);

        cur = o2;
        while (!set.contains(cur)) {
            cur = map.get(cur);
        }
        return cur;
    }

    private void fun(TreeNode root, Map<Integer, Integer> map) {
        if (root == null ) {
            return;
        }

        //把当前根节点的左右孩子，以及两个孩子的父节点存入map中
        if(root.left!=null) {
            map.put(root.left.val, root.val);
        }else{
            map.put(null, root.val);
        }
        if(root.right!=null) {
            map.put(root.right.val, root.val);
        }else{
            map.put(null, root.val);
        }



        //递归左右孩子
        fun(root.left, map);
        fun(root.right, map);
    }



    //力扣要求返回 TreeNode
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // write code here
        Map<TreeNode,TreeNode> map2=new HashMap<>();
        map2.put(root,root);
        fun2(root,map2);

        //用Set 从下到上，遍历记录o1的祖先链
        Set<TreeNode> set=new HashSet<>();
        TreeNode cur= p;
        while (map2.get(cur) != cur) {
            set.add(cur);
            cur=map2.get(cur);
        }
        set.add(cur);

        cur=q;
        while (!set.contains(cur)) {
            cur=map2.get(cur);
        }
        return cur;
    }


    private void fun2(TreeNode root, Map<TreeNode,TreeNode> map) {
        if (root==null) {
            return;
        }

        //把当前根节点的左右孩子，以及两个孩子的父节点存入map中
        map.put(root.left,root);
        map.put(root.right,root);

        //递归左右孩子
        fun2(root.left,map);
        fun2(root.right,map);
    }
}
